package com.primary.linkedList;

import java.util.Stack;

/**
 * @author: yyh
 * @description:删除链表的倒数第N个节点：https://leetcode.cn/leetbook/read/top-interview-questions-easy/xn2925/
 * @date: 2022/7/20 11:16
 */
public class RemoveNthFromEnd {

    /**
     * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
     *
     *
     * 提示：
     * 链表中结点的数目为 sz
     * 1 <= sz <= 30
     * 0 <= Node.val <= 100
     * 1 <= n <= sz
     *
     * 进阶：你能尝试使用一趟扫描实现吗？
     */

    
    public static void main(String[] args) {
        ListNode c = new ListNode(4);
        ListNode b = new ListNode(3,c);
        ListNode a = new ListNode(2, b);
        ListNode head = new ListNode(1, a);

        removeNthFromEnd_1(head,4);
    }

    /**
     *      * 输入：head = [1,2,3,4,5], n = 2
     *      * 输出：[1,2,3,5]
     *      *
     *      * 输入：head = [1], n = 1
     *      * 输出：[]
     *      *
     *      * 输入：head = [1,2], n = 1
     *      * 输出：[1]
     */
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        Stack<ListNode> stack = new Stack<>();
        stack.push(head);
        ListNode next = head;
        while ((next = next.next) != null) {
            stack.push(next);
        }
        ListNode pre = null;
        for (int i = 1; i <= n; i++) {
            if (i == n - 1) {
                pre = stack.pop();
            } else  {
                stack.pop();
            }
        }
        if (!stack.empty()) {
            stack.pop().next = pre;
        }else {
            head = pre;
        }
        
        return head;
    }

    /**
     * 一次遍历
     */
    public static ListNode removeNthFromEnd_1(ListNode head, int n) {
        // 1-> 2-> 3-> 4-> 5-> 6->null  n = 3
        ListNode a = head;
        ListNode b = head;
        for (int i = 0; i < n; i++) {
            a = a.next;
        }
        //a = 3,b = 1
        if (a == null) {
            //删掉head
            head = head.next;
            return head;
        }
        while ((a = a.next) !=null) {
            b = b.next;
            //a = 4,b=2
            //a = 5,b=3
            //a = 6,b=3
        }
        b.next = b.next.next;
        return head;
    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}